package a00_LeetCode.Tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author quan
 * @Description 最小深度：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 *
 * 说明: 叶子节点是指没有子节点的节点。什么是叶子节点，左右孩子都为空的节点才是叶子节点！ *
 * @Date 2023/3/31 11:46
 */
public class Num111_MinDepth {
    /**
     * 方法1：递归法
     */
    /*public int minDepth(TreeNode root){
        //(1)注意：这个不能用最大深度的递归直接写：下面这样写是错误的。这种情况只存在于左右子树都存在的情况，返回的是1+左右子树中的最小深度
        //如果左子树不存在，那么返回的是1+右子树的最小深度；如果右子树不存在，返回的是1+左子树的最小深度
        *//*int leftDepth = getDepth(node->left);
        int rightDepth = getDepth(node->right);
        int result = 1 + min(leftDepth, rightDepth);
        return result;*//*
        //(2)正确写法
        if(root == null){
            return 0;
        }
        if(root.left== null){
            return 1+minDepth(root.right);
        }
        if(root.right== null){
            return 1+minDepth(root.left);
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        return Math.min(leftDepth,rightDepth)+1;
    }*/
    /**
     * 方法2：递归法：层序遍历当碰见第一个左右节点都为null的节点，则该节点的最近叶子节点
     */
    public int minDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int depth = 0;
        while (!deque.isEmpty()){
            //层序遍历的层数就是二叉树的深度
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.pop();
                //比求最大深度多一行代码！！！
                if(node.left == null && node.right == null){
                    //是叶子节点。因为是从上往下遍历，所以该值就是最小值
                    return depth;
                }
                if(node.left != null){
                    deque.offer(node.left);
                }
                if(node.right != null){
                    deque.offer(node.right);
                }
            }
        }
        return depth;
    }
}
